package test;

/**
 * @Author: gc
 * @Date: 2024/6/27 19:54
 * @explain:
 **/

import java.util.Stack;

public class FloydShortestPath {

    static final int INF = Integer.MAX_VALUE;

    // 使用迭代方式打印从起点到终点的最短路径上的所有节点
    public static void printPathIterative1(int[][] next, int start, int end, char[] vertex) {
        if (start == end) {
            System.out.print(vertex[start] + " ");
        } else {
            Stack<Integer> stack = new Stack<>();
            while (end != start) {
                stack.push(end);
                end = next[start][end];
                if (end == -1) {
                    System.out.println(vertex[start] + " to " + vertex[end] + "不连通");
                    return;
                }
            }
            stack.push(start);
            while (!stack.isEmpty()) {
                System.out.print(vertex[stack.pop()] + " ");
            }
        }
        System.out.println(); // 在路径打印完成后添加换行
    }

    // Floyd-Warshall算法
    public static void floydWarshall(int[][] graph, char[] vertex, int[] AdditionalCost) {
        int V = graph.length;
        int[][] dist = new int[V][V];
        int[][] next = new int[V][V];

        // 初始化权重矩阵和前驱关系矩阵
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
                if (i == j) {
                    next[i][j] = -1; // 自身到自身的路径没有"下一个节点"
                } else if (graph[i][j] != INF) {
                    next[i][j] = i; // 直接相连的下一个节点就是自己
                } else {
                    next[i][j] = -1; // 无路径设置为-1
                }
            }
        }

        System.out.println("*****初始化权重矩阵*****");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == INF) {
                    System.out.print("INF" + " ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
        System.out.println();
        System.out.println("*****初始化前驱关系节点矩阵*****");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (next[i][j] != -1) {
                    System.out.print(vertex[next[i][j]] + " ");
                } else {
                    System.out.print(next[i][j] + " ");
                }
            }
            System.out.println();
        }
        // 算法核心
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                        int cost = dist[i][k] + dist[k][j]+AdditionalCost[k];
                        if(cost<dist[i][j]){
                            dist[i][j] = cost;
                            next[i][j] = next[k][j]; // 更新下一个节点
                        }
                    }
                }
            }
        }

        // 打印起点到终点，最短路径，中间节点及最短路径上的所有节点
        System.out.println("------------------打印结果------------------");
        for (int i = 0; i < V; i++) {
            for (int j = i + 1; j < V; j++) {
                System.out.print("(" + vertex[i] + "->" + vertex[j] + ")" +
                        "  最低成本:" + dist[i][j] +
                        "  " + "规划途经点:");
                printPathIterative1(next, i, j, vertex);
            }
        }
    }

    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F'};
        int[] AdditionalCost = {100, 110, 130, 120, 65, 115};
        //INF代表不连通，0代表自身到自身，成本为0
        int graph[][] = {
                {0, 8, 30, 156, INF, INF},
                {8, 0, INF, INF, 44, 114},
                {30, INF, 0, 198, INF, INF},
                {156, INF, 198, 0, 2, 12},
                {INF, 44, INF, 2, 0, INF},
                {INF, 114, INF, 12, INF, 0},
        };
        floydWarshall(graph, vertex,AdditionalCost);
    }
}
